/** 
Definition for singly-linked list.*/
#include<iostream>
#include<vector>
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head;  //采用快慢指针遍历链表
        ListNode *quick= head;
        int flag = false;   //当第一次相遇后，flag=true
        //因为第一次相遇后，快指针比慢指针多走环节点数(假设为b)*n次
        //而环节点的分支处，在此处的部数为从head到此分支处的距离(假设为a) + b*n
        //所以，第一次相遇后，快指针退化成慢指针速度，并重新恢复到head处
        //目的是求出这个a的距离，第二次相遇即可
        while(quick!=NULL){
            //向下寻找
            if(slow->next!=NULL)
                slow = slow->next;
            if(quick->next!=NULL && quick->next->next!=NULL)
                quick = flag ? quick->next:quick->next->next;
            else
                break;  //无法继续遍历说明没有环，到头了
            
            if(slow == quick && !flag){
                flag = true;
                quick = head;
            }
            if(slow == quick)   //不用else if，因为可能头节点就是环的一部分
                return slow;
        }
        return NULL;
    }
};